package arithmetic;

import java.util.HashSet;
import java.util.Set;

/**
 * @author jie
 * @version 创建时间：2018年4月27日 上午7:43:13
 * 链表翻转 206
 * https://leetcode-cn.com/problems/reverse-linked-list/
 * <p>
 * （1）递归反转法：在反转当前节点之前先反转后续节点。
 * 这样从头结点开始，层层深入直到尾结点才开始反转指针域的指向。
 * 简单的说就是从尾结点开始，逆向反转各个结点的指针域指向，其过程图如下所示：
 * head：是前一结点的指针域（PS：前一结点的指针域指向当前结点）
 * head.getNext()：是当前结点的指针域（PS：当前结点的指针域指向下一结点）
 * reHead：是反转后新链表的头结点（即原来单链表的尾结点）
 */
public class A_01_ReverseHead {
    public static void main(String[] args) {
        Node head = new Node(0);
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        head.setNext(node1);
        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
        node5.setNext(node6);

        //node6.setNext(node2);// 设置 环
        // 打印反转前的链表
        printLink(head);


        // 反转链表
//        resersalDG(head);//递归linke
        head = reverseDGTemplete(head);//递归linke
//		head = reversal(head);//循环

        //2个点 各自翻转
//		head = SwapNodesInPairs24(head);

        //判断是否有 Circle
//        boolean b = linkHasCircle(head);
//        boolean b1 = linkHasCircleTwoPoint(head);
        System.out.println("\n**************************");
        // 打印反转后的结果
        printLink(head);


    }

    private static void printLink(Node head) {
        while (null != head) {
            System.out.print(head.getData() + " ");
            try {
                Thread.sleep(10);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            head = head.getNext();
        }
    }

    /**
     * 思路：
     * 1、保存上一个节点，当前节点指向上一个节点，然后再进行下一个节点变更，直到终点。
     *
     * @param head
     * @return
     */
    private static Node reversal(Node head) {
        Node current = head;
        Node pre = null;
        while (current != null) {
            Node next = current.getNext();//临时保存 下一个节点
            current.setNext(pre);//反转---
            pre = current;// 终点 pre是最后一个节点
            current = next;//最后 current == null
        }
        return pre;
    }


    private static Node reverseDGTemplete(Node node) {
        if (node == null || node.getNext() == null) {
            // last is not null .last.next == null
            return node;//orign last node,new Head.
        }

        Node last = reverseDGTemplete(node.getNext());
        //reverse
        Node next = node.getNext();
        next.setNext(node);//反转之前的节点
        node.setNext(null);//反转当前节点。否则，origin HEAD -> origin HEAD2.
        return last;
    }

    // 递归，在反转当前节点之前先反转后续节点
    private static Node resersalDG(Node node) {
        //终止条件
        if (node == null || node.getNext() == null) {
            return node; //返回最有一个节点。
        }
        //查找条件
        Node lastNode = resersalDG(node.getNext());

        //node-->5 node-->4 node-->3 node-->2 node-->1 node-->0 ,没有6 最有一个。代替while 循环，倒序。  if (head == null || head.getNext() == null)
        //node-->6 node-->5 node-->4 node-->3 node-->2 node-->1 node-->0 ,  if (node == null ) ,
//		System.out.print(" node-->"+node.getData());
        //so ,node 从倒数第二个节点开始。因为，node.getNext() 为最后一个节点，node.getnext().getnext ==null.

        //current node:
        Node current = node;//是因为，从 node5 开始的。要取到6
        Node last = node.getNext();//是因为，从 node5 开始的。要取到6


        //反转  //最后一个节点 指向  倒数第二个节点
        last.setNext(current);
        //当前指向null ,为了0 指向null
        current.setNext(null);

        return lastNode;//返回新链表head的值 倒数第一个节点
    }


    //2个节点互相翻转个 ,节点0-1-2-3 变为 1-0-3-2 ，如果是单数最后不变
    public static Node SwapNodesInPairs24(Node head) {
        //a,b,c,d--> b,a,d,c.手动画图，斩断节点路径。
        Node originB = head.getNext();//b
        Node preCut = null;//first pri a is null
        Node cut = head;
        while (cut != null && cut.getNext() != null) {
            Node b = cut.getNext();//b
            //上一节点指向下一节点
            if (preCut != null) {
                preCut.setNext(b);//pri->a >>> pri -> b
            }
            Node c = b.getNext();
            cut.setNext(c);//a -> c
            b.setNext(cut);//b->a
            preCut = cut;//pri = a
            cut = c;// cur = c
        }

        if (originB != null) {//b!=null, a<->b
            return originB;
        }
        return head;//originA
    }

    //判断链表是否有环

    //1、单位时间内是否走到最后 null
    //2、利用 set 去重
    //3、龟兔赛跑， 如果乌龟兔子重合。。。
    public static boolean linkHasCircle(Node head) {
        Set<Node> hashSet = new HashSet<Node>();
        hashSet.add(head);
        while (head.getNext() != null) {
            Node next = head.getNext();
            if (hashSet.contains(next))
                return true;
            hashSet.add(next);
            head = next;
        }
        return false;
    }

    //一个指针走1步，第二个指针走多步
    public static boolean linkHasCircleTwoPoint(Node head) {
        Node slow = head;
        Node fast = head;

        while (slow != null && fast != null && fast.getNext() != null) {
            fast = fast.getNext().getNext();
            slow = slow.getNext();
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
}

class Node {
    private int Data;// 数据域
    private Node Next;// 指针域

    public Node(int Data) {
        // super();
        this.Data = Data;
    }

    public int getData() {
        return Data;
    }

    public void setData(int Data) {
        this.Data = Data;
    }

    public Node getNext() {
        return Next;
    }

    public void setNext(Node Next) {
        this.Next = Next;
    }
}
